package com.datastructures2.graph.最短路径;

import com.datastructures.graph.Bag;
import edu.princeton.cs.algs4.In;

/**
 * 加权有向图
 * @author MaoLin Wang
 * @date 2020/2/2319:15
 */
public class EdgeWeightedDigraph {
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;
    private int E;
    private int[] indegree;             // indegree[v] = indegree of vertex v

    private Bag<DirectedEdge>[] adj;

    public EdgeWeightedDigraph(int v){
        this.V=v;
        this.E=0;
        this.adj=new Bag[V];
        this.indegree = new int[V];

        for (int i = 0; i < V; i++) {
            adj[i]=new Bag<>();
        }
    }
    public EdgeWeightedDigraph(In in) {
        this(in.readInt());
        int E = in.readInt();
        if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
        for (int i = 0; i < E; i++) {
            int v = in.readInt();
            int w = in.readInt();
            validateVertex(v);
            validateVertex(w);
            double weight = in.readDouble();
            addEdge(new DirectedEdge(v, w, weight));
        }
    }

    public void addEdge(DirectedEdge edge) {
        int from = edge.from();
        validateVertex(from);
        int to = edge.to();
        validateVertex(to);
        adj[from].add(edge);
        indegree[to]++;
        E++;
    }
    public Iterable<DirectedEdge> adj(int v) {
        validateVertex(v);
        return adj[v];
    }

    /**
     * 顶点v的出度
     * @param v
     * @return
     */
    public int outdegree(int v) {
        validateVertex(v);
        return adj[v].size();
    }

    /**
     * 顶点v的入度
     * @param v
     * @return
     */
    public int indegree(int v) {
        validateVertex(v);
        return indegree[v];
    }
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }

    public Iterable<DirectedEdge> edges(){
        Bag<DirectedEdge>bag=new Bag<>();
        for (int v = 0; v < V; v++) {
            for (DirectedEdge edge:adj[v]){
                bag.add(edge);
            }
        }
        return bag;
    }
    private void validateVertex(int v) {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + NEWLINE);
        for (int v = 0; v < V; v++) {
            s.append(v + ": ");
            for (DirectedEdge e : adj[v]) {
                s.append(e + "  ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }
}
